package puzzle.projecteuler.p200;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;

import astudy.util.AdvMath;

public class Problem143C {

	/**
	 * a^2 = q^2 + r^2 + q*r
	 * b^2 = p^2 + q^2 + p*q
	 * c^2 = p^2 + r^2 + p*r
	 * p<=q<=r
	 * 
	 * 
	 * 
	 * answer	: 30758397
	 * time cost: 430016 ms
	 * 
	 * @param args
	 */
	public static void main(String[] args) {
		
		long s = System.currentTimeMillis();
		int m = 120000;
		List<int[]> rs = solutions(m);
		System.out.println((System.currentTimeMillis()-s) + " ms");
		//将rs转换成map格式，以方便后面的操作
		Map<Integer, List<Integer>> tmp = new HashMap<Integer, List<Integer>>();
		for (int[] ts: rs) {
			int p = ts[0];
			int q = ts[1];
			if (tmp.get(p) == null) {
				tmp.put(p, new ArrayList<Integer>());
			}
			if (tmp.get(q) == null) {
				tmp.put(q, new ArrayList<Integer>());
			}
			tmp.get(p).add(q);
			tmp.get(q).add(p);
		}
		Map<Integer, Integer[]> map = new HashMap<Integer, Integer[]>();
		for (int k: tmp.keySet()) {
			List<Integer> a = tmp.get(k);
			Integer[] b = a.toArray(new Integer[a.size()]);
			Arrays.sort(b);
			map.put(k, b);
		}
		//查找满足条件的解
		Set<Integer> set = new HashSet<Integer>();
		for (int[] ts: rs) {
			int p = ts[0];
			int q = ts[1];
			Integer[] ps = map.get(p);
			for (Integer r: map.get(q)) {
				if (Arrays.binarySearch(ps, r) > -1 && p+q+r<=m) {
					set.add(p+q+r);
					System.out.println(p + "," + q + "," + r + ":" + (p+q+r));
				}
			}
		}
		//计算所有不同的p+q+r的和
		long sum = 0;
		for (int x: set) {
			sum += (long)x;
		}
		System.out.println("count = " + set.size());
		System.out.println("sum = " + sum);
		System.out.println((System.currentTimeMillis()-s) + " ms");
	}
	
	/**
	 * 方程 p^2 + q^2 + p*q = z^2
	 * 满足 z <= m 的所有正整数解(p,q)
	 * 
	 * (2p+q)^2 + 3*q^2 = (2*z)^2
	 */
	public static List<int[]> solutions(int m) {
		
		List<int[]> rs = new ArrayList<int[]>();
		for (int z = 1; z <= m; z ++) {
			List<int[]> tmp = find2(2*z);
			for (int[] pair: tmp) {
				int a = pair[0];
				int b = pair[1];
				if (a > b) {
					int q = b;
					int p = (a -b)/2;
					System.out.println(z + "^2="+ p + "^2 + " + p + "*" + q + " + " + q + "^2");
					rs.add(new int[]{p, q});
				}
			}

		}
		return rs;
	}
	
	/**
	 * find solution of 3*x^2 +３３ y^2 = c, gcd(x,y) = 1
	 * @param c
	 * @return
	 */
	public static List<int[]> find(int c) {
		
		List<int[]> rs = new ArrayList<int[]>();
		for (int x = 1; x < Math.sqrt(c/3.0); x ++) {
			int y2 = c - 3*x*x;
			int y = (int)Math.sqrt(y2);
			if (y*y == y2 && AdvMath.gcd(x, y) == 1) {
				rs.add(new int[]{x, y});
			}
		}
		return rs;
	}
	
	/**
	 * find solution of a^2 +３ 3*b^2 = c^2
	 * 注意： 
	 * 		a^2 +３３ 3*b^2 = c^2
	 * => 	c = (3*x^2+y^2)*d/2, a = |3*x^2-y^2|*d/2, b = d*x*y, 	gcd(x, y) = 1, x,y奇数
	 * or 	c = (3*x^2+y^2)*d,   a = |3*x^2-y^2|*d,   b = 2*d*x*y, 	gcd(x, y) = 1
	 * 
	 * @param c
	 * @return
	 */
	private static List<int[]> find2(int c) {

		Map<String, int[]> map = new HashMap<String, int[]>();
		//c = (3*x^2+y^2)*d/2, a = |3*x^2-y^2|*d/2, b = d*x*y, 	gcd(x, y) = 1, x,y奇数
		for (int d = 1; d <= 2*c; d ++) {
			if (2*c%d == 0) {
				List<int[]> tmp = find(2*c/d);
				for (int[] pair: tmp) {
					int x = pair[0];
					int y = pair[1];
					if (x%2 != 0 && y%2 != 0) {
						int a = Math.abs(3*x*x-y*y)*d/2;
						int b = d*x*y;
						String key = (c + "^2="+ a + "^2 + 3*" + b + "^2");
						map.put(key, new int[]{a, b});
					}
				}
			}
		}
		//c = (3*x^2+y^2)*d,   a = |3*x^2-y^2|*d,   b = 2*d*x*y, 	gcd(x, y) = 1
		for (int d = 1; d <= c; d ++) {
			if (c%d == 0) {
				List<int[]> tmp = find(c/d);
				for (int[] pair: tmp) {
					int x = pair[0];
					int y = pair[1];
					int a = Math.abs(3*x*x-y*y)*d;
					int b = 2*d*x*y;
					String key = (c + "^2="+ a + "^2 + 3*" + b + "^2");
					map.put(key, new int[]{a, b});
				}
			}
		}
		List<int[]> rs = new ArrayList<int[]>();
		for (String key: map.keySet()) {
//			System.out.println(key);
			rs.add(map.get(key));
		}
		return rs;
	}
}
